1. Field of the Invention
This invention relates generally to memory circuits, and more specifically to low power search techniques in content addressable memory circuits using sample words to save power in compare lines.
2. Description of the Related Art
A content addressable memory (CAM) semiconductor device is a device that allows the entire contents of the memory to be searched and matched instead of having to specify one or more particular memory locations in order to retrieve data from the memory. Thus, a CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks.
CAMs provide performance advantages over conventional memory devices having conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired search term, or comparand, against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a non-CAM based database of 1000 entries may take ten separate search operations whereas a CAM device with 1000 entries may be searched in a single operation, resulting in significant time and processing savings. Internet routers often include a CAM for searching the address of specified data, allowing the routers to perform fast address searches to facilitate more efficient communication between computer systems over computer networks.
Conventional CAMs typically include a two-dimensional row and column content addressable memory core array of cells. In such an array, each row typically contains an address, pointer, or bit pattern entry. In this configuration, a CAM may perform “read” and “write” operations at specific addresses as is done in conventional random access memories (RAMs). However, unlike RAMs, data “search” operations that simultaneously compare a bit pattern of data against an entire list (i.e., column) of pre-stored entries (i.e., rows) can be performed.
FIG. 1A shows a simplified block diagram of a conventional CAM 100. The CAM 100 includes a data bus 102 for communicating data, an instruction bus 104 for transmitting instructions associated with an operation to be performed, and an output bus 106 for outputting a result of the operation. For example, in a search operation, the CAM 100 may output a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data.
As mentioned above, to perform a search operation a CAM includes a plurality of bit pattern entries, each comprising a series of CAM cells coupled to a local match line. FIG. 1B is a schematic diagram showing a prior art bit pattern entry 120 in a conventional CAM. The bit pattern entry 120 includes a plurality of CAM cells 122 coupled to a local match line 124. In addition, the bit pattern entry 120 includes a current generator 126 and precharge circuitry 128 coupled to the local match line 124. The local match line 124 is further coupled to an inverter 130, which is coupled to an inverter latch 132. Each CAM cell 122 is also coupled to a pair of compare lines K0 and K1. Although, for clarity, only one CAM cell 122 is shown coupled to compare lines in FIG. 1B, it should be noted that all the CAM cells 122 are actually coupled to compare lines.
During a search operation, the precharge circuitry 128 precharges the match line 124 to a predictable state, which is generally low, to prepare for the search. The compare data, known as the comparand, is then compared to the bit pattern entry 120. Specifically, compare lines, such as compare lines K0 and K1, are used to compare the comparand to the data stored in the CAM cells 122. The current generator 126 begins to supply current to the match line 124. As the compare data is compared to the data stored in each CAM cell 122, the CAM cell will ground the match line 124 if the data stored in the CAM cell 122 does not match the compare data. Thus, if any CAM cell 122 does not match the compare data, the match line 124 will be pulled low. Conversely, if all the CAM cells 122 in the bit pattern entry 120 match the comparand, the match line 124 will remain high. The signal from the match line 124 is then sent through an inverter 130, and then to the inverter latch 132, which provides a high or low output, as described in greater detail below.
FIG. 1C is a diagram showing exemplary search signals 150 for a conventional CAM. The search signals 150 include an external clock 152, a first compare line K0 154, a second compare line K1 156, an internal clock 158, a match line 160, and a search output 162. As previously mentioned, during a search the compare lines 154 and 156 are used to provide search data to a particular CAM cell. Each compare line 154 and 156 will be set to either high or low, depending on the search data. Typically the compare lines K0 154 and K1 156 are set to the inverse of each other, however, when using a ternary CAM cell both compare lines 154 and 156 may be set to the same value. In the example of FIG. 1C, a first set of search data is placed on the compare lines for the first and second external clock cycle 150a and 150b. Then the search data is inverted in the third and fourth external clock cycle 150c and 150d. In addition, the data stored in the CAM cell matches the first set of search data, during the first and second external clock cycle 150a and 150b, and does not match during the third and fourth external clock cycle 150c and 150d.
To set the compare lines 154 and 156 to their appropriate values in a conventional CAM, each compare line 154/156 is first set to a predictable state of zero, or low. Then, one of the compare lines is asserted high. As shown in FIG. 1C, at the rising edge of the first external clock cycle 150a, both compare lines 154 and 156 are set low. Shortly thereafter, one of the compare lines is asserted high, in this case compare line K0 154, thus in the first external clock cycle 150a, K0 154 is asserted high and K1 remains low.
Next, at the rising edge of the second external clock cycle 150b, compare line K0 154 is again set to a predictable state of zero. In this case, the search data for this particular CAM cell remains the same in the second external clock cycle 150b, thus compare line K0 154 is again asserted high shortly after the rising edge of the second external clock cycle 150b. In a similar manner, both compare lines K0 154 and K1 156 are set to a state of zero at the beginning of the third external clock cycle 150c. This time the comparand changes, thus switching compare lines K0 154 and K1 156 such that K1 156 is asserted high shortly after the rising edge of the third external clock cycle 150c, while K0 154 remains low. At the rising edge of the fourth clock cycle 150d, both compare lines 154 and 156 are set to zero. The search data remains the same for the fourth external clock cycle 150d, thus compare line K1 156 is again asserted high shortly after the rising edge of the fourth clock cycle 150d.
Thus, in a conventional CAM the compare lines are pulsed to compare the search data to the data stored in the CAM cell. This results in two transitions for every clock cycle of the external clock 152, regardless of the actual data being placed on the compare lines. As will be explained in greater detail subsequently, each transition requires increased power in the CAM to overcome the capacitance of the compare line.
Continuing with the above example, an internal clock 158 is used to control the search results in the conventional CAM. The internal clock 158 is an inverted clock, which is pulsed slightly after the compare lines 154 and 156 are set to the appropriate search value. As mentioned above, in the example of FIG. 1C the search data matches the data stored in the CAM cell during the first and second external clock cycle 150a and 150b, and does not match during the third and fourth external clock cycle 150c and 150d. Hence, at leading edge of the first internal clock cycle 158a, the match line 160 begins to ramp up, since the data stored in the CAM cell matches the comparand in the first external clock cycle 150a.
The rising match line 160 causes the inverted latch to output a high search output signal 162 during the first internal clock cycle. The precharge circuitry coupled to the match line 160 then causes the match line 160 to discharge and go low at the trailing edge of the first internal clock pulse 158a. As a result, during the leading edge of the second internal clock pulse 158b the output signal 162 is low. The output signal 162 then transitions to high after the match line 160 ramps to a sufficient level, later during the second internal clock pulse 158b. During the third and fourth external clock pulses 150c and 150d, the data stored in the CAM cell does not match the comparand. Hence, both the match line 160 and the output signal 162 are low during the third and fourth internal clock pulses 158c and 158d. Thus, during consecutive match results, the output signal 162 of the conventional CAM generally must transition from low to high during each internal clock cycle.
Each output 162 for each bit pattern entry of the CAM is coupled to a global match line, which is a long line that provides the search results to other areas of the CAM for further processing, such as to priority encoders. The long length of the global match lines results in each global match line having a large capacitance. As a result, every transition on a global match line requires a large amount of power to overcome the large capacitance. Since the output signals from the bit pattern entries propagate to the global match lines, every transition in the output signal results in a large power drain on the CAM. A similar result occurs with respect to the compare lines, each transition in the compare lines requires increased power from the CAM to overcome the capacitance of the compare line.
In view of the foregoing, there is a need for low power search methods for use in content addressable memory circuits. The methods should reduce the power required to perform searches in the CAM, and decrease the amount of transitions required during search operations.